import java.lang.reflect.Array;
import java.util.Arrays;


public class QuickInsertion {
	private static int cutOfPoint = 0;
	
	public static void sort(int[] a, int cutoff) {
            cutOfPoint = cutoff;
            sort(a, 0, a.length-1);
	}
	
	private static void sort(int[] a, int lo, int hi) {
            if (hi-lo <= cutOfPoint && hi-lo>1) {
                    insertionSort(a, lo, hi);
            }else{
                    if (hi <= lo) return;
                    int j = partition(a, lo, hi);
                    sort(a, lo, j-1);
                    sort(a, j+1, hi);
            }
	}
	
	private static int partition(int[] a, int lo, int hi) {
            int i = lo, j = hi+1;
            int v = a[lo];
            while(true)
            {
                    while(a[++i] < v) if (i == hi) break;
                    while(a[--j] > v) if (j == lo) break;
                    if (i >= j) {
                            break;
                    }
                    exch(a, i, j);
            }
            exch(a, lo, j);
            return j;
	}
	
	private static void exch(int[] a, int i, int j) {
            int k = a[i];
            a[i] = a[j];
            a[j] = k;
	}
	
	public static void insertionSort(int[] a, int lo, int hi) {
            for(int i = lo+1; i < hi; i++) {
                    for(int j = i;j > 0 && (a[j] < a[j-1]); j--) {
                            exch(a, j, j-1);
                    }
            }
	}

    public static void main(String[] args){
        int t = 100;
        int m = 100;
        int m_max = 1000000;
        int c_max = 80;

        //indexes:
        //0 = mean execution time
        //1 = standard deviation

        for(int i = m; i<=m_max; i*=10){
            double[][] results = new double[c_max+1][2];
            double[] res = new double[t];
            for(int c=0; c<=c_max; c++){
                for(int j = 0; j<t; j++){
                    int[] data = new int[i];
                    for(int k=0; k<i; k++)
                        data[k] = StdRandom.uniform(i*10);
                    long time = System.nanoTime();
                    sort(data,c);
                    res[j] = (double) (System.nanoTime() - time);
                }
                results[c][0] = StdStats.mean(res);
                results[c][1] = StdStats.stddev(res);
            }
            double best = 1000000000000.0;
            int best_c = 0;

            //Find the best cut-off for this experiment..
            for(int c = 0; c<=c_max; c++){
                if(results[c][0]<best){
                    best = results[c][0];
                    best_c = c;
                }
            }

            //Print results..
            StdOut.println("N = "+i+":");
            StdOut.println("Mean running time: "+results[0][0]);
            StdOut.println("Stanrard deviation: "+results[0][1]);

            StdOut.println();

            if(results[0][0]-results[0][1]>best){
                StdOut.println("Most improvement with cut-off: "+best_c);
                StdOut.println("Mean running time: "+results[best_c][0]);
                StdOut.println("Stanrard deviation: "+results[best_c][1]);
                StdOut.println("Improvement in percent: "+(results[0][0]-results[best_c][0])/results[0][0]*100+"%");
            }else{
                StdOut.println("Couldn't see a difference..");
            }
            StdOut.println();
        }
    }

   /*public static void main(String[] args){
        int[] test = {1,8,2,5,41,6,2,53,9,2,5,7};
        sort(test, 0);
        if(sorted(test)) System.out.println("Succes. Result:");
        for(int i : test){
            System.out.println(i);
        }
   }

    private static boolean sorted(int[] data) {
        int last = data[0];
        for(int i : data){
            if(last>i) return false;
            last = i;
        }
        return true;
    }*/
}
